package com.yanceysong.codetop.s41_s50;

public class S50_Mid_8_字符串转换整数_atoi {
    /**
     * .S50_Mid_8_字符串转换整数 (atoi)
     * .<p>
     * .LeetCode链接：<a href="https://leetcode.cn/problems/string-to-integer-atoi/">https://leetcode.cn/problems/string-to-integer-atoi/</a>
     * .<p>
     * .题目描述：
     * .实现一个 myAtoi(string s) 函数，将字符串转换成 32 位有符号整数（类似 C/C++ 中的 atoi）。
     * .转换规则：
     * .1. 跳过前导空格
     * .2. 可选的符号位 '+' 或 '-'
     * .3. 读取尽可能多的连续数字字符形成数值
     * .4. 忽略数字之后的任何字符
     * .5. 如果数值溢出，截断到 INT_MAX (2147483647) 或 INT_MIN (-2147483648)
     * .6. 如果不含有效数字，返回 0
     * .<p>
     * .示例：
     * .输入: "42"                输出: 42
     * .输入: "   -42"            输出: -42  (跳过前导空格, 符号为 '-')
     * .输入: "4193 with words"   输出: 4193 (数字后面内容忽略)
     * .输入: "words and 987"     输出: 0    (首字符非法)
     * .输入: "-91283472332"      输出: -2147483648 (下溢，截断)
     * .输入: "+-12"              输出: 0    ('+' 后紧跟 '-' 非法, 没有数字)
     * .输入: "00000-42a1234"     输出: 0    (连续数字后 '-' 终止)
     * .<p>
     * .核心标签：字符串 / 模拟 / 有限状态机 / 溢出处理
     * .<p>
     * .关键洞察：
     * .- 溢出检测不能先乘再判断，应在乘法前通过 (result > (MAX - digit)/10) 判定
     * .- 读取阶段一旦遇到非数字字符立即停止，不回退
     * .- 符号只能出现一次且必须紧跟在前导空格之后
     * .<p>
     * .ASCII 状态流（简化）：
     * .[开始] --(空格)--> [开始]
     * .[开始] --('+'/'-')--> [符号]
     * .[开始|符号] --(数字)--> [数字]
     * .[数字] --(数字)--> [数字]
     * .其它字符：停止，进入 [结束]
     * .<p>
     * .时间复杂度：O(n)，单次线性扫描
     * .空间复杂度：O(1)，仅常数变量
     */
    public int myAtoi(String s) {
        // 1. 去除前导和尾部空格（题目仅需跳过前导空格；trim() 也能满足但会再处理尾部，这里保留即可）
        s = s.trim();
        if (s.isEmpty()) {
            return 0;
        }
        int signFlag = 1; // 记录符号，默认正数
        int startIdx = 0; // 当前扫描起点
        // 2. 处理符号位
        if (s.charAt(0) == '-') {
            signFlag = -1;
            startIdx++;
        } else if (s.charAt(0) == '+') {
            startIdx++;
        }
        int resultNumber = 0; // 累积构造的结果
        // 3. 读取数字并处理溢出
        for (int i = startIdx; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') { // 非数字，终止
                break;
            }
            int digit = c - '0';
            // 溢出检测：如果 resultNumber * .10 + digit > Integer.MAX_VALUE
            if (resultNumber > (Integer.MAX_VALUE - digit) / 10) {
                return signFlag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            resultNumber = resultNumber * 10 + digit;
        }
        return resultNumber * signFlag;
    }

    /**
     * .有限状态机实现（扩展方法，帮助理解）。
     * .状态：start(起始/空格)、sign(符号)、number(数字)、end(结束)
     */
    public int myAtoiFSM(String s) {
        if (s == null || s.isEmpty()) return 0;
        long value = 0; // 使用 long 方便检测溢出
        int signFlag = 1;
        int state = 0; // 0:start 1:sign 2:number 3:end
        for (int i = 0; i < s.length() && state != 3; i++) {
            char c = s.charAt(i);
            switch (state) {
                case 0: // start
                    if (c == ' ') {
                        // stay in start
                    } else if (c == '+' || c == '-') {
                        signFlag = (c == '-') ? -1 : 1;
                        state = 1;
                    } else if (c >= '0' && c <= '9') {
                        value = c - '0';
                        state = 2;
                    } else {
                        state = 3; // end, invalid
                    }
                    break;
                case 1: // sign
                case 2: // number
                    if (c >= '0' && c <= '9') {
                        value = value * 10 + (c - '0');
                        // 溢出裁剪
                        if (signFlag == 1 && value > Integer.MAX_VALUE) return Integer.MAX_VALUE;
                        if (signFlag == -1 && -value < Integer.MIN_VALUE) return Integer.MIN_VALUE;
                        state = 2;
                    } else {
                        state = 3; // end
                    }
                    break;
                default:
                    state = 3;
            }
        }
        value *= signFlag;
        if (value > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (value < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        return (int) value;
    }

    public static void main(String[] args) {
        S50_Mid_8_字符串转换整数_atoi solution = new S50_Mid_8_字符串转换整数_atoi();
        System.out.println("=== 字符串转换整数 (atoi) 测试开始 ===");
        // 基本示例
        testCase(solution, "42", 42);
        testCase(solution, "   -42", -42);
        testCase(solution, "4193 with words", 4193);
        testCase(solution, "words and 987", 0);
        testCase(solution, "-91283472332", -2147483648);
        testCase(solution, "+1", 1);
        testCase(solution, "+-12", 0);
        testCase(solution, "00000-42a1234", 0);
        testCase(solution, "   +0 123", 0);
        testCase(solution, "2147483647", 2147483647);
        testCase(solution, "2147483648", 2147483647);
        testCase(solution, "-2147483648", -2147483648);
        testCase(solution, "-2147483649", -2147483648);
        testCase(solution, "   ", 0);
        testCase(solution, "", 0);
        testCase(solution, "--2", 0);
        testCase(solution, "+ 2", 0);
        testCase(solution, "  -0012a42", -12);
        testCase(solution, "  -001200", -1200);
        testCase(solution, "3.14159", 3);
        testCase(solution, "-3.14159", -3);
        testCase(solution, "   +004500", 4500);
        testCase(solution, "-000000", 0);
        testCase(solution, "-000001", -1);

        System.out.println("\n=== 所有测试完成 ===");
    }

    private static void testCase(S50_Mid_8_字符串转换整数_atoi solution, String input, int expected) {
        int ansBasic = solution.myAtoi(input);
        int ansFSM = solution.myAtoiFSM(input);
        boolean consistent = ansBasic == ansFSM;
        System.out.printf("输入: %-15s | basic:%11d FSM:%11d | 一致:%s | 期望:%11d %s\n",
                input, ansBasic, ansFSM, consistent, expected, (ansBasic == expected ? "✓" : "✗"));
        assert ansBasic == expected : "basic实现结果不符合期望";
        assert ansFSM == expected : "FSM实现结果不符合期望";
    }
}
